#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
	vector<int> countSmaller(vector<int>& nums) {
		vector<int>count(nums.size(), 0);
		vector<int>indices(nums.size(), 0);
		for (int i = 0; i < nums.size(); i++) {
			indices[i] = i;
		}
		sorthelper(nums, count, indices, 0, nums.size() - 1);
		return count;
	}
private:
	void sorthelper(vector<int>& nums, vector<int>& count, vector<int>& indices, int left, int right) {
		if (left >= right)return;
		int mid = left + (right - left) / 2;
		sorthelper(nums, count, indices, left, mid);
		sorthelper(nums, count, indices, mid + 1, right);
		merge(nums, count, indices, left, mid, right);
	}
	void merge(vector<int>& nums, vector<int>& count, vector<int>& indices, int left, int mid, int right) {
		int i = left, j = mid + 1, k = 0;
		int countright = 0;
		vector<int>temp(right - left + 1);
		while (i <= mid && j <= right) {
			if (nums[indices[i]] > nums[indices[j]]) { countright++; temp[k++] = indices[j++]; }
			else { count[indices[i]] += countright; temp[k++] = indices[i++]; }
		}
		while (i <= mid) { count[indices[i]] += countright; temp[k++] = indices[i++]; }
		while (j <= right) { temp[k++] = indices[j++]; }
		for (int p = 0; p < k; p++) {
			indices[left + p] = temp[p];
		}
	}
};